package LeetCode.month03.day72;

import java.util.*;

/**
 * @author 16778
 * @date 2025/10/11 8:11
 * @description
 */
public class No3186 {


    public long maximumTotalDamage(int[] power) {
        Arrays.sort(power);
        int n = power.length;
        int[] arr = new int[power[n-1]+1];
        for (int i : power) {
            arr[i]+=i;
        }
        return rob(arr);
    }

    private long rob(int[] arr) {
        if(arr==null||arr.length==0)
            return 0;
        int n = arr.length;
        if(n==1) return arr[0];
        if(n==2) return Math.max(arr[0],arr[1]);
        if(n==3) return Math.max(Math.max(arr[0],arr[1]),arr[2]);
        long[] dp = new long[n];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0],arr[1]);
        dp[2] = Math.max(arr[2],dp[1]);
        for (int i = 3; i < n; i++) {
            dp[i] = Math.max(dp[i-1],Math.max(dp[i-3]+arr[i],dp[i-2]));
        }
        return dp[n-1];
    }

    public long maximumTotalDamage2(int[] power) {
        TreeMap<Integer,Integer> count = new TreeMap<>();
        for (int p : power) {
            count.put(p, count.getOrDefault(p, 0) + 1);
        }
        List<int[]> vec = new ArrayList<>();
        vec.add(new int[]{-1000000000,0});
        for (Map.Entry<Integer,Integer> e : count.entrySet()) {
            vec.add(new int[]{e.getKey(), e.getValue()});
        }
        int n = vec.size();
        long[] f = new long[n];
        long mx = 0, ans = 0;
        int j = 1;
        for (int i = 1; i < n; i++) {
            while (j < i && vec.get(j)[0] < vec.get(i)[0] - 2) {
                mx = Math.max(mx, f[j]);
                j++;
            }
            f[i] = mx + 1L * vec.get(i)[0] * vec.get(i)[1];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }

    public long maximumTotalDamage3(int[] power){
        Map<Integer,Integer> cnt = new HashMap<>();
        for (int i : power) {
            cnt.merge(i, 1, Integer::sum);
        }
        int n = cnt.size();
        int [] a = new int[n];
        int i = 0;
        for (Integer x : cnt.keySet()) {
            a[i++]=x;
        }
        Arrays.sort(a);

        long memo[] = new long[n+1];
        int j =0;
        for (int k = 0; k < n; k++) {
            int x = a[k];
            while ( a[j] + 2 < x) {
                j++;
            }
            memo[k+1] =Math.max(memo[j] + (long) x * cnt.get(x), memo[k]);
        }
        return memo[n];
    }
}
